Ordered multi-field rules-based classifications are an important part of any network access/routing environment. Rules are defined in priority order across multiple fields in a packet and the field values can have wild card bits like subnets. Incoming packets are matched with the rules in priority order and an action determined by the first rule matching each packet is taken. Ordered multi-field rules-based classification is used in multiple areas such as access control lists (ACLs), policy based routing, packet filtering, software defined networks, and so on. As network speeds increase and protocols become more complex, fast updating of these rules becomes more and more important with applications such as open flow and software defined networks needing update rates of more than thousands per second. Instead of matching the incoming packet with the rules one by one, the rules are organized as a tree of longest prefix matching (LPM) tables chained together to simulate ordered matching. The process of matching an action to a packet traverses the tree ending up with the action of the first rule that matches the packet. The entire set of rules is analyzed for field value relationships to derive the tree structure. Whenever there is an update, the new rule set is analyzed and a new tree is generated. The conventional rebuild approach limits how fast updates can be made and uses a large amount of transient memory to build a new tree and atomically switch to the new tree before deleting the old tree.
It would be desirable to have a method and/or apparatus for implementing incremental updates for ordered multi-field classification rules when represented by a tree of longest prefix matching (LPM) tables without having to rebuild the entire tree.